package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript:
 * @date: 2021/3/18 21:31
 * @version: 1.0
 */
public class Q39_IsBalancedTree {
    public static void main(String[] args) {

    }

    /**
     * 左子树、右子树各自是平衡二叉树吗（需要收集子树是否是平衡二叉树）
     * 如果1成立，还需要收集左子树和右子树的高度，如果高度相差不超过1那么当前这棵树才是平衡二叉树（需要收集子树的高度）
     */
    //需要收集的平衡二叉树的信息
    private static class Info{
        boolean isBalanced;
        int height;
        Info(boolean isBalanced, int height){
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    //递归体的定义：（这里高度之差不超过1中的left.height - right.height == 0容易被忽略）
    private static Info isBalanceTree(TreeNode root){
        if (root==null){
            return new Info(true,0);
        }
        Info left=isBalanceTree(root.left);
        Info right=isBalanceTree(root.right);
        if (!left.isBalanced ||!right.isBalanced){
            return new Info(false,0);
        }
        if ((left.height-right.height==1)
                ||(left.height-right.height==-1)
                || (left.height-right.height==0)){
            return new Info(true,Math.max(left.height,right.height)+1);
        }
        return new Info(false,0);
    }



    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public void TreeNode(int val){
            this.val=val;
        }
    }
}
